package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Triangle {
	
	public static void main(String[] args) {
		Integer[] a1 = {2};
		Integer[] a2 = {3, 4};
		Integer[] a3 = {6, 5, 7};
		Integer[] a4 = {4, 1, 8, 3};
		
		List<List<Integer>> test = new ArrayList<List<Integer>>();
		test.add(Arrays.asList(a1));
		test.add(Arrays.asList(a2));
		test.add(Arrays.asList(a3));
		test.add(Arrays.asList(a4));
		
		Integer[] b1 = {2};
		Integer[] b2 = {3, 4};
		Integer[] b3 = {6, 5, 1};
		Integer[] b4 = {4, 1, 8, 1};
		
		List<List<Integer>> test1 = new ArrayList<List<Integer>>();
		test1.add(Arrays.asList(b1));
		test1.add(Arrays.asList(b2));
		test1.add(Arrays.asList(b3));
		test1.add(Arrays.asList(b4));
		
		Triangle tri = new Triangle();
		System.out.println(tri.minimumTotal(test));
		System.out.println(tri.minimumTotal(test1));
		
	}
	
	/**
	 * [2],
  	  [3,4],
     [6,5,7],
    [4,1,8,3]
	 * @param triangle
	 * @return
	 */
	
    public int minimumTotal(List<List<Integer>> triangle) {
    	if (triangle == null || triangle.size() == 0) return 0;
    	int row = triangle.size();
    	int[] res = new int[row];
    	
    	// init last row, and then go from bottom up
    	for (int i = 0; i < row; i++) {
    		res[i] = triangle.get(row - 1).get(i);
    	}
    	
    	for (int i = row - 2; i >= 0; i--) {
    		int col = triangle.get(i).size();
    		for (int j = 0; j < col; j++) {
    			res[j] = Math.min(res[j], res[j + 1]) + triangle.get(i).get(j);
    		}
    	}
    	
    	return res[0];
    }
}
